#pragma once
#include <gecode/int.hh>
#include <gecode/search.hh>
#include <gecode/minimodel.hh>

using namespace Gecode;

class Sudoku : public Space
{
protected:
	IntVarArray l;
public:

	Sudoku(int * problem, IntConLevel option = ICL_DEF) : l(*this, 81, 1, 9)
	{
		const int n = 3;
		const int nn = 9;
		Matrix<IntVarArray> m(l, nn, nn);

		// Constraints for rows and columns
		for (int i=0; i<nn; i++) 
		{
			distinct(*this, m.row(i), option);
			distinct(*this, m.col(i), option);
		}

		// Constraints for squares
		for (int i=0; i<nn; i+=n) 
		{
			for (int j=0; j<nn; j+=n) {
				distinct(*this, m.slice(i, i+n, j, j+n), option);
			}
		}

		// Fill-in predefined fields
		for (int i=0; i<nn; i++)
		{
			for (int j=0; j<nn; j++)
			{
				int v = *(problem+i*nn+j);
				if(v != 0) rel(*this, m(i,j), IRT_EQ, v);
			}
		}

		branch(*this, l, INT_VAR_SIZE_MIN, INT_VAL_MIN);

	}

	Sudoku(bool share, Sudoku& s) : Space(share, s) 
	{
		l.update(*this, share, s.l);
	}

	virtual Space* copy(bool share) 
	{
		return new Sudoku(share,*this);
	}

	void print(void) const {
		const int nn = 9;
		for (int i=0; i<nn; i++)
		{
			for (int j=0; j<nn; j++)
			{
				std::cout << l[i+j*nn] <<" ";
			}
			std::cout<<std::endl;
		}
		
	}

	~Sudoku(void)
	{
	}
};

static int examples[][9][9] = {
    {
	{0,0,0, 2,0,5, 0,0,0},
	{0,9,0, 0,0,0, 7,3,0},
	{0,0,2, 0,0,9, 0,6,0},
	
	{2,0,0, 0,0,0, 4,0,9},
	{0,0,0, 0,7,0, 0,0,0},
	{6,0,9, 0,0,0, 0,0,1},
    
	{0,8,0, 4,0,0, 1,0,0},
	{0,6,3, 0,0,0, 0,8,0},
	{0,0,0, 6,0,8, 0,0,0}
    },{
	{3,0,0, 9,0,4, 0,0,1},
	{0,0,2, 0,0,0, 4,0,0},
	{0,6,1, 0,0,0, 7,9,0},

	{6,0,0, 2,4,7, 0,0,5},
	{0,0,0, 0,0,0, 0,0,0},
	{2,0,0, 8,3,6, 0,0,4},
    
	{0,4,6, 0,0,0, 2,3,0},
	{0,0,9, 0,0,0, 6,0,0},
	{5,0,0, 3,0,9, 0,0,8}
    },{
	{0,0,0, 0,1,0, 0,0,0},
	{3,0,1, 4,0,0, 8,6,0},
	{9,0,0, 5,0,0, 2,0,0},
    
	{7,0,0, 1,6,0, 0,0,0},
	{0,2,0, 8,0,5, 0,1,0},
	{0,0,0, 0,9,7, 0,0,4},
    
	{0,0,3, 0,0,4, 0,0,6},
	{0,4,8, 0,0,6, 9,0,7},
	{0,0,0, 0,8,0, 0,0,0}
    },{	// Fiendish puzzle April 21, 2005 Times London
	{0,0,4, 0,0,3, 0,7,0},
	{0,8,0, 0,7,0, 0,0,0},
	{0,7,0, 0,0,8, 2,0,5},
    
	{4,0,0, 0,0,0, 3,1,0},
	{9,0,0, 0,0,0, 0,0,8},
	{0,1,5, 0,0,0, 0,0,4},
    
	{1,0,6, 9,0,0, 0,3,0},
	{0,0,0, 0,2,0, 0,6,0},
	{0,2,0, 4,0,0, 5,0,0}
    },{	// This one requires search
	{0,4,3, 0,8,0, 2,5,0},
	{6,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,1, 0,9,4},
    
	{9,0,0, 0,0,4, 0,7,0},
	{0,0,0, 6,0,8, 0,0,0},
	{0,1,0, 2,0,0, 0,0,3},
    
	{8,2,0, 5,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,5},
	{0,3,4, 0,9,0, 7,1,0}
    },{	// Hard one from http://www.cs.mu.oz.au/671/proj3/node5.html
	{0,0,0, 0,0,3, 0,6,0},
	{0,0,0, 0,0,0, 0,1,0},
	{0,9,7, 5,0,0, 0,8,0},

	{0,0,0, 0,9,0, 2,0,0},
	{0,0,8, 0,7,0, 4,0,0},
	{0,0,3, 0,6,0, 0,0,0},

	{0,1,0, 0,0,2, 8,9,0},
	{0,4,0, 0,0,0, 0,0,0},
	{0,5,0, 1,0,0, 0,0,0}
    },{ // Puzzle 1 from http://www.sudoku.org.uk/bifurcation.htm
	{1,0,0, 9,0,7, 0,0,3},
	{0,8,0, 0,0,0, 0,7,0},
	{0,0,9, 0,0,0, 6,0,0},
	{0,0,7, 2,0,9, 4,0,0},
	{4,1,0, 0,0,0, 0,9,5},
	{0,0,8, 5,0,4, 3,0,0},
	{0,0,3, 0,0,0, 7,0,0},
	{0,5,0, 0,0,0, 0,4,0},
	{2,0,0, 8,0,6, 0,0,9}
    },{ // Puzzle 2 from http://www.sudoku.org.uk/bifurcation.htm
	{0,0,0, 3,0,2, 0,0,0},
	{0,5,0, 7,9,8, 0,3,0},
	{0,0,7, 0,0,0, 8,0,0},
	{0,0,8, 6,0,7, 3,0,0},
	{0,7,0, 0,0,0, 0,6,0},
	{0,0,3, 5,0,4, 1,0,0},
	{0,0,5, 0,0,0, 6,0,0},
	{0,2,0, 4,1,9, 0,5,0},
	{0,0,0, 8,0,6, 0,0,0}
    },{ // Puzzle 3 from http://www.sudoku.org.uk/bifurcation.htm
	{0,0,0, 8,0,0, 0,0,6},
	{0,0,1, 6,2,0, 4,3,0},
	{4,0,0, 0,7,1, 0,0,2},
	{0,0,7, 2,0,0, 0,8,0},
	{0,0,0, 0,1,0, 0,0,0},
	{0,1,0, 0,0,6, 2,0,0},
	{1,0,0, 7,3,0, 0,0,4},
	{0,2,6, 0,4,8, 1,0,0},
	{3,0,0, 0,0,5, 0,0,0}
    },{ // Puzzle 4 from http://www.sudoku.org.uk/bifurcation.htm
	{3,0,5, 0,0,4, 0,7,0},
	{0,7,0, 0,0,0, 0,0,1},
	{0,4,0, 9,0,0, 0,3,0},
	{4,0,0, 0,5,1, 0,0,6},
	{0,9,0, 0,0,0, 0,4,0},
	{2,0,0, 8,4,0, 0,0,7},
	{0,2,0, 0,0,7, 0,6,0},
	{8,0,0, 0,0,0, 0,9,0},
	{0,6,0, 4,0,0, 2,0,8}
    },{ // Puzzle 5 from http://www.sudoku.org.uk/bifurcation.htm
	{0,0,0, 7,0,0, 3,0,0},
	{0,6,0, 0,0,0, 5,7,0},
	{0,7,3, 8,0,0, 4,1,0},
	{0,0,9, 2,8,0, 0,0,0},
	{5,0,0, 0,0,0, 0,0,9},
	{0,0,0, 0,9,3, 6,0,0},
	{0,9,8, 0,0,7, 1,5,0},
	{0,5,4, 0,0,0, 0,6,0},
	{0,0,1, 0,0,9, 0,0,0}
    },{ // Puzzle 6 from http://www.sudoku.org.uk/bifurcation.htm
	{0,0,0, 6,0,0, 0,0,4},
	{0,3,0, 0,9,0, 0,2,0},
	{0,6,0, 8,0,0, 7,0,0},
	{0,0,5, 0,6,0, 0,0,1},
	{6,7,0, 3,0,1, 0,5,8},
	{9,0,0, 0,5,0, 4,0,0},
	{0,0,6, 0,0,3, 0,9,0},
	{0,1,0, 0,8,0, 0,6,0},
	{2,0,0, 0,0,6, 0,0,0}
    },{ // Puzzle 7 from http://www.sudoku.org.uk/bifurcation.htm
	{8,0,0, 0,0,1, 0,4,0},
	{2,0,6, 0,9,0, 0,1,0},
	{0,0,9, 0,0,6, 0,8,0},
	{1,2,4, 0,0,0, 0,0,9},
	{0,0,0, 0,0,0, 0,0,0},
	{9,0,0, 0,0,0, 8,2,4},
	{0,5,0, 4,0,0, 1,0,0},
	{0,8,0, 0,7,0, 2,0,5},
	{0,9,0, 5,0,0, 0,0,7}
    },{ // Puzzle 8 from http://www.sudoku.org.uk/bifurcation.htm
	{6,5,2, 0,4,8, 0,0,7},
	{0,7,0, 2,0,5, 4,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,6,4, 1,0,0, 0,7,0},
	{0,0,0, 0,8,0, 0,0,0},
	{0,8,0, 0,0,4, 5,6,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,8, 6,0,7, 0,2,0},
	{2,0,0, 8,9,0, 7,5,1}
    },{ // Puzzle 9 from http://www.sudoku.org.uk/bifurcation.htm
	{0,0,6, 0,0,2, 0,0,9},
	{1,0,0, 5,0,0, 0,2,0},
	{0,4,7, 3,0,6, 0,0,1},
	{0,0,0, 0,0,8, 0,4,0},
	{0,3,0, 0,0,0, 0,7,0},
	{0,1,0, 6,0,0, 0,0,0},
	{4,0,0, 8,0,3, 2,1,0},
	{0,6,0, 0,0,1, 0,0,4},
	{3,0,0, 4,0,0, 9,0,0}
    },{ // Puzzle 10 from http://www.sudoku.org.uk/bifurcation.htm
	{0,0,4, 0,5,0, 9,0,0},
	{0,0,0, 0,7,0, 0,0,6},
	{3,7,0, 0,0,0, 0,0,2},
	{0,0,9, 5,0,0, 0,8,0},
	{0,0,1, 2,0,4, 3,0,0},
	{0,6,0, 0,0,9, 2,0,0},
	{2,0,0, 0,0,0, 0,9,3},
	{1,0,0, 0,4,0, 0,0,0},
	{0,0,6, 0,2,0, 7,0,0}
    },{ // Puzzle 11 from http://www.sudoku.org.uk/bifurcation.htm
	{0,0,0, 0,3,0, 7,9,0},
	{3,0,0, 0,0,0, 0,0,5},
	{0,0,0, 4,0,7, 3,0,6},
	{0,5,3, 0,9,4, 0,7,0},
	{0,0,0, 0,7,0, 0,0,0},
	{0,1,0, 8,2,0, 6,4,0},
	{7,0,1, 9,0,8, 0,0,0},
	{8,0,0, 0,0,0, 0,0,1},
	{0,9,4, 0,1,0, 0,0,0}
    },{ // From http://www.sudoku.org.uk/discus/messages/29/51.html?1131034031
	{2,5,8, 1,0,4, 0,3,7},
	{9,3,6, 8,2,7, 5,1,4},
	{4,7,1, 5,3,0, 2,8,0},

	{7,1,5, 2,0,3, 0,4,0},
	{8,4,9, 6,7,5, 3,2,1},
	{3,6,2, 4,1,0, 0,7,5},

	{1,2,4, 9,0,0, 7,5,3},
	{5,9,3, 7,4,2, 1,6,8},
	{6,8,7, 3,5,1, 4,9,2}
    }
};

